Let A^Z be the Cantor space of bi-infinite sequences in a finite alphabet A,and let sigma be the shift map on A^Z. A `cellular automaton' is a continuous,sigma-commuting self-map Phi of A^Z, and a `Phi-invariant subshift' is aclosed, (Phi,sigma)-invariant subset X of A^Z. Suppose x is a sequence in A^Zwhich is X-admissible everywhere except for some small region we call a`defect'. It has been empirically observed that such defects persist underiteration of Phi, and often propagate like `particles'. We characterize themotion of these particles, and show that it falls into several regimes, rangingfrom simple deterministic motion, to generalized random walks, to complexmotion emulating Turing machines or pushdown automata. One consequence is thatsome questions about defect behaviour are formally undecidable.
展开▼
